package leecode

func isPalindromeM(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	//寻找链表中间节点
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	newList := reserveListM(slow.Next)
	slow.Next = nil
	l1, l2 := head, newList
	for l1 != nil && l2 != nil {
		if l1.Val != l2.Val {
			return false
		}
		l1 = l1.Next
		l2 = l2.Next
	}
	return true
}

func reserveListM(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}
